import random
import math

def get_cost(n, adj_mat, sol):
    """
    :param n: number of vertices, e.g. 2
    :param adj_mat: adjacency matrix, e.g. [[0,1], [1,0]]
    :param sol: solution, e.g. [1,0]
    """
    return sum([adj_mat[sol[_]][sol[(_ + 1) % n]] for _ in range(n)])

def get_new_sol_swap(sol, i, j):
    new_sol = sol.copy()
    new_sol[i], new_sol[j] = new_sol[j], new_sol[i]
    return new_sol

def get_delta_swap(n, adj_mat, sol, i, j):
    delta = adj_mat[sol[i - 1]][sol[j]] + adj_mat[sol[j]][sol[(i + 1) % n]] + \
            adj_mat[sol[j - 1]][sol[i]] + adj_mat[sol[i]][sol[(j + 1) % n]] - \
            adj_mat[sol[i - 1]][sol[i]] - adj_mat[sol[i]][sol[(i + 1) % n]] - \
            adj_mat[sol[j - 1]][sol[j]] - adj_mat[sol[j]][sol[(j + 1) % n]]
    if j - i == 1 or i == 0 and j == n - 1:
        delta += 2 * adj_mat[sol[i]][sol[j]]
    return delta

def get_new_sol_2opt(sol, i, j):
    new_sol = sol.copy()
    new_sol[i:j+1] = new_sol[i:j+1][::-1]
    return new_sol

def get_delta_2opt(n, adj_mat, sol, i, j):
    delta = adj_mat[sol[i - 1]][sol[j]] + adj_mat[sol[i]][sol[(j + 1) % n]] - \
            adj_mat[sol[i - 1]][sol[i]] - adj_mat[sol[j]][sol[(j + 1) % n]]
    if i == 0 and j == n - 1:
        delta = 0
    return delta

def get_new_sol_move(sol, i, j):
    new_sol = sol.copy()
    new_sol[i:j+1] = new_sol[i:i+1] + new_sol[j:j+1] + new_sol[i+1:j]
    return new_sol

def get_delta_move(n, adj_mat, sol, i, j):
    delta = adj_mat[sol[i]][sol[j]] + adj_mat[sol[j]][sol[(i + 1) % n]] + adj_mat[sol[j - 1]][sol[(j + 1) % n]] - \
            adj_mat[sol[i]][sol[(i + 1) % n]] - adj_mat[sol[j - 1]][sol[j]] - adj_mat[sol[j]][sol[(j + 1) % n]]
    if i == n - 1 and j == 0:
        delta = 0
    return delta

def get_new_sol_CIM(sol, i, j):
    new_sol = sol.copy()
    new_sol = new_sol[:i][::-1] + new_sol[i:][::-1]
    return new_sol

def get_delta_CIM(n, adj_mat, sol, i, j):
    delta = adj_mat[sol[0]][sol[i]] + adj_mat[sol[i]][sol[n - 1]] + adj_mat[sol[i - 1]][sol[(i + 1) % n]] - \
            adj_mat[sol[i - 1]][sol[i]] - adj_mat[sol[i]][sol[(i + 1) % n]] - adj_mat[sol[0]][sol[n - 1]]
    if i == 0 and i == n - 1:
        delta = 0
    return delta

class Init:
    def __init__(self, points, dim, og, distmat):
        self.points = points
        self.dim = dim
        self.og = og
        self.distmat = distmat
        self.group = []
        
    def ccw(self, a, b, c):
        return ((b[1] - a[1]) * (c[0] - b[0])) - ((c[1] - b[1]) * (b[0] - a[0]))

    def compute(self, next):
        start = self.points[0]
        if start[0] == next[0]:
            return 999999
        slope = (start[1] - next[1]) / (start[0] - next[0])
        return slope

    def Graham_Scan(self, points):
        if len(points) < 3:
            raise ValueError("Graham_Scan requires at least 3 points")

        Min = float('inf')
        index = 0
        for i in range(len(points)):
            if points[i][0] < Min:
                Min = points[i][0]
                index = i
            elif points[i][0] == Min and points[i][1] < points[index][1]:
                index = i

        points[0], points[index] = points[index], points[0]
        points = points[:1] + sorted(points[1:], key=self.compute)

        convex_hull = []
        for p in points:
            while len(convex_hull) > 1 and self.ccw(convex_hull[-2], convex_hull[-1], p) >= 0:
                convex_hull.pop()
            convex_hull.append(p)

        person = [int(x[2]) for x in convex_hull if 0 <= int(x[2]) < self.dim]
        if not person:
            raise ValueError("Graham_Scan produced empty or invalid convex hull")
        return person

    def newCreate(self):
        try:
            stp = self.Graham_Scan(self.points)
            if not all(isinstance(x, int) and 0 <= x < self.dim for x in stp):
                raise ValueError(f"Invalid indices in stp: {stp}")
            
            origin = list(range(self.dim))
            for x in stp:
                if x in origin:
                    origin.remove(x)
                else:
                    print(f"Warning: {x} not in origin list {origin}")
            
            sto = origin.copy()
            for i in range(self.og):
                person = stp.copy()
                origin = sto.copy()
                toto, totp = len(sto), len(stp)
                while toto > 0:
                    if not origin:
                        print("Error: Empty origin list")
                        break
                    x = origin[random.randint(0, toto-1)]
                    mn, posmn = float('inf'), 0
                    for j in range(totp):
                        if j < totp-1:
                            Dis = self.distmat[person[j]][x] + self.distmat[x][person[j+1]] - self.distmat[person[j]][person[j+1]]
                        else:
                            Dis = self.distmat[person[j]][x] + self.distmat[x][person[0]] - self.distmat[person[j]][person[0]]
                        if Dis < mn:
                            mn = Dis
                            posmn = j
                    person.insert(posmn+1, x)
                    totp += 1
                    if x in origin:
                        origin.remove(x)
                    else:
                        print(f"Warning: {x} not in origin list {origin}")
                        break
                    toto -= 1
                self.group.append(person)
            if self.og == 1:
                return self.group[0]
            return self.group
        except Exception as e:
            print(f"Error in newCreate: {e}")
            raise

def tnm_selection(n, adj_mat, sol, max_tnm, mut_md):
    get_new_sol = mut_md[0]
    get_delta = mut_md[1]
    cost = get_cost(n, adj_mat, sol)
    best_delta = math.inf
    best_i = best_j = -1
    for _ in range(max_tnm):
        i, j = random.sample(range(n), 2)
        i, j = (i, j) if i < j else (j, i)
        delta = get_delta(n, adj_mat, sol, i, j)
        if delta < best_delta:
            best_delta = delta
            best_i = i
            best_j = j
    new_sol = get_new_sol(sol, best_i, best_j)
    new_cost = cost + best_delta
    return new_sol, new_cost

def Search(n, adj_mat, sol, mut_md):
    get_new_sol = mut_md[0]
    get_delta = mut_md[1]
    cost = get_cost(n, adj_mat, sol)
    i, j = random.sample(range(n), 2)
    i, j = (i, j) if i < j else (j, i)
    delta = get_delta(n, adj_mat, sol, i, j)
    new_sol = get_new_sol(sol, i, j)
    new_cost = cost + delta
    return new_sol, new_cost